package chase.java.algorithm;


import chase.java.unit.Edge;
import chase.java.unit.Point;

import java.util.*;

public class AStar {


    public static Edge execute(Point start,Point goal,List<Edge> edges){
        Edge path ;
        //将路网最近点作为起点的周边点
        boolean sf = nearest(start,edges);
        boolean gf = nearest(goal,edges);

        path = path(start,goal);

        //将添加到路网上的多余的点和多余的周边点删除,防止影响下一次检索
        remove(start, sf);
        remove(goal, gf);

        return path;
    }

    private static void remove(Point goal, boolean flag) {
        if(flag){
            for (Point point : goal.near) {
                point.near.remove(goal);
                for(Point near: point.near){
                    near.near.remove(point);
                }
            }
        }
        else{
            for (Point point : goal.near) {
                point.near.remove(goal);
            }
        }
    }


    //找到点到一条线段的最近路线
    static Point getVer(Point pt,Point begin, Point end) {

        Point retVal = new Point();
        double dx = begin.getX() - end.getX();
        double dy = begin.getY() - end.getY();
        if(Math.abs(dx) < 0.00000001 && Math.abs(dy) < 0.00000001 ) {
            retVal = begin;
            return retVal;
        }

        double u = (pt.getX() - begin.getX())*(begin.getX() - end.getX()) +
                (pt.getY() - begin.getY())*(begin.getY() - end.getY());
        u = u/((dx*dx)+(dy*dy));

        //如果垂足不在线段上就返回null
        if(u>0)
            return begin;
        else if(u<-1)
            return end;
        retVal.setX(begin.getX() + u*dx);
        retVal.setY(begin.getY() + u*dy);
        return retVal;
    }



    //找到路网的最短距离,并返回点
    static boolean nearest(Point local,List<Edge> edges){
        //使用flag来表示点是新增加的
       boolean flag = false;
       Point target = null;
       double dis = Double.MAX_VALUE;
       Point begin = null;
       Point end = null;

        for(Edge e: edges){
            for(int i=0;i<e.length()-1;++i){
                Point vertical = getVer(local,e.get(i),e.get(i+1));
                if(distance(vertical,local) < dis){
                    target = vertical;
                    dis = distance(target,local);
                    begin = e.get(i);
                    end = e.get(i+1);
                }
            }
        }
        assert target != null;

        //关联鼠标点和最近点
        target.near.add(local);
        local.near.add(target);

        //如果点原本不存在,还需要关联点和其左右点
        if(target != begin && target != end){
            begin.near.add(target);
            end.near.add(target);
            target.near.add(begin);
            target.near.add(end);
            flag = true;
        }
        return flag;
    }

    //设置所有点的周边的点
    public static void setNear(List<Edge> edges){
        List<Point> points = new ArrayList<>();
        for(Edge e: edges){
            for(int i=0;i<e.length();++i){
                if(i>0)
                    e.get(i).near.add(e.get(i-1));
                if(i<e.length()-1)
                    e.get(i).near.add(e.get(i+1));
                points.add(e.get(i));
            }
        }

        for(Point p1: points){
            for(Point p2: points){
                if(p1!=p2 && p1.equals(p2))
                    p1.near.addAll(p2.near);
            }
        }

    }

    //曼哈顿距离
//    static double distance(Point a, Point b){
//        return Math.abs(a.getX()-b.getX()) + Math.abs(a.getY()-b.getY());
//    }


    //欧式距离
    static double distance(Point a, Point b){
        return Math.sqrt(Math.pow(a.getX()-b.getX(),2) + Math.pow(a.getY()-b.getY(),2));
    }

    //得到两点之间的代价
    static double cost(Point a, Point b){
        return distance(a,b);
    }

    //获得图上两点的最短的路径
    static Edge path(Point start, Point goal){

        //代价队列
        PriorityQueue<Point> frontier = new PriorityQueue<>();
        //已被访问点队列
        Set<Point> visited = new HashSet<>();

        //初始化起点
        start.steps = 0;
        start.setCost(0);
        start.pre = null;
        frontier.add(start);

        //得到的最短路径
        Edge shortestPath = new Edge();
        Point p = null;

        while(!frontier.isEmpty()){
            //取出第一个元素,并设置已访问
            Point cur = frontier.poll();
            visited.add(cur);

            //如果第一个点是终点退出循环
            if(cur.equals(goal)){
                p = cur;
                break;
            }

            //遍历第一个点周边的点,并将未访问的点添加到代价队列
            for(Point near: cur.near){
                if(visited.contains(near))
                    continue;
                near.pre=cur;
                //需要自己定义各一个代价函数的计算方式
                near.steps = near.pre.steps + cost(near,near.pre);
                near.setCost(near.steps+cost(near,goal));
                frontier.add(near);
            }
        }

        //根据pre指针取出最短路径
        //修改为新创建点, 需要和生成的垂足一起参与缩放
        while(p != null){
            shortestPath.add(new Point(p.getX(),p.getY()));
            p = p.pre;
        }

        return shortestPath;
    }

    //读取测试用的简单路径
//    public static List<Edge> read(){
//        List<Edge> edges = new ArrayList<>();
//
//        File file = new File("src/chase/java/resource/simplePath.txt");
//        try {
//            BufferedReader fis = new BufferedReader(new FileReader(file));
//            String str;
//            while((str=fis.readLine())!=null){
//                String[] points=str.split(" ");
//                Edge edge = new Edge();
//                for(String index: points){
//                    String[] candidate = index.split(",");
//                    edge.add(new Point(Double.parseDouble(candidate[0]),Double.parseDouble(candidate[1])));
//
//                }
//                edges.add(edge);
//
//            }
//
//
//        } catch (Exception e) {
//            e.printStackTrace();
//        }
//
//        return edges;
//    }
//
//
//    //测试最短路径与画图
//    public static void test() {
//        List<Edge> edges = read();
//        new Draw().draw(edges);
//    }

    }
